In digital communication systems employing multi-channel or multi-carrier transmission, the most effective allocation of bits to the channels has been discussed in the literature. The well-known solution from information theory, analogized to pouring water over a terrain defined by the noise/attenuation of the channel transform characteristic, has been found to insure efficient use of signal power within limits defined by aggregate power and power spectral density mask limits. However, the method in some instances may not go as far as possible in exploiting available power imposed by these limits.
For heuristic purposes, the prior art and the invention are discussed in terms of N quadrature amplitude modulation (QAM) channels with a uniform symbol rate and a non-uniform (unique to each channel) QAM constellation. QAM, a form of combined amplitude and phase modulation, represents k-bit sets of data by modulating two (orthogonal) quadrature carriers, cos 2.pi.f.sub.c t and sin 2.pi.f.sub.c t to generate a pulse whose phase and amplitude convey the encoded k-bits of information. The QAM signal tone can be viewed as a phasor in the complex plane, each distinguishable phasor representing a unique state of the tone identified with one unique value in a range. Thus, if the channel and signal power are such that 4 separate phasors can be reliably distinguished, the scheme allows two bits to be represented. For 3 bits to be represented, 8 phasors must be distinguished and so on. The number of different phasors or states that are distinguishable in a single tone (pulse), the QAM constellation, is limited by the signal to noise ratio of the channel and limits imposed by external standards as discussed below.
In a DMT modem, a transmission frequency band is separated into N sub-bands or frequency bins, each corresponding to one QAM channel. In a non-ideal channel each sub-band has a different capacity as a result of the variation of noise and attenuation with frequency. In addition, external standards impose limits on the aggregate power of a signal (the power applied in all sub-band channels) and a cap on the power as a function of frequency defined by a power spectral density mask.
The power spectral density mask may be dictated by the standard used in a particular country implementing the standard (such as A.N.S.I. standard T1.413-1995). The mask may also be a design constraint intentionally imposed by a modem designer for some other reason. For example, a designer may intentionally impose a constraint that no more than n bits are to be transmitted on transmit channel frequency. Similarly, the designer may impose a constraint that a minimum of bits (or no bits) must be transmitted on a particular tone or frequency. For example, the power limit for frequencies or tones between 0 and 200 kilohertz must be less than --40 dBm/Hz (a power level referenced to one milliwatt over 1 Hz bandwidth). Above 200 kHz (to frequencies in the megahertz of spectrum), the constraint may be -34 dBm/Hz.
Referring to FIG. 1, the attenuation +noise characteristics of a medium can be graphically represented by a floor in a power spectral graph. The lower curve, the channel transform characteristic A represents this floor, that is, the combined effect of noise and attenuation as a function of frequency. A certain margin of power is required to meet or exceed the minimum threshold of a signal for reliable data transmission. In other words, the power of a signal in a given sub-band must be sufficiently high to carry a minimal (1-bit) QAM tone to obtain a predefined bit error rate. The minimum margin, that required to transmit a single bit, is represented by curve B. Curve C represents the limits imposed by a power spectral density mask imposed by an external communications standard. The other limit is on the aggregate power, also defined by an external communication standard, e.g., ANSI Standard T1.413-1995 limits the total power for all sub-bands to 100 mWatts. Some coding techniques, such as Wei code described in American National Standard for Telecommunications--Network and Customer Installation Interfaces--Asymmetric Digital Subscriber Line Metallic Interface, ANSI T1.413-1995, may also require a minimum number of bits in a frequency band if the band is to convey any information at all. In other words, if the power spectral density mask limit may require that less energy be used than the minimum required to transmit a single bit.
Note that the minimum allowable size of the power margin is, in part, arbitrary since, to an extent, it is defined in terms of some a priori rules and technical criteria (which are arbitrary to the extent that they establish a dividing line between acceptable and unacceptable error rates; Bit Error Rate or BER) for the given communication system. Note also that the size of the margin available for a given sub-band corresponds to the dimension of the constellation that can be represented in a signal carried in that QAM channel. That is, the larger the margin in a band, the greater the number of states that can be reliably distinguished in that band and the larger the constellation that can be used.
The above context creates a bit-allocation problem. That is, given the constraints, how should bits be allocated among the available QAM channels to provide the highest possible data rates? DSL modems that use DMT modulation concentrate the transmitted information in the frequency sub-bands that have the minimum attenuation and noise. The optimum distribution of transmission power is obtained by distributing the power according to the well-known "water pouring" analogy as described in Robert G. Gallagher, Information Theory and Reliable Communication, John Wiley and Sons, New York, 1968. Such optimal distribution requires a strategy for allocating bits to the sub-bands for the idealized situation where the channel sub-bands approach zero width (.DELTA.f.fwdarw.0). For discrete bits, the applicable metaphor could be described as an ice-cube pouring analogy.
DSL technology was conceived to maximize the throughput on twisted pair copper wiring with attendant background noise, time-variant Far End Cross Talk (FEXT) and Near End Cross Talk (NEXT). To determine the transform characteristic of the channel, the modems negotiate during an initial channel signal-to-noise ratio (SNR) estimation procedure. During the procedure, the transmitter sends a known pseudo noise (PN) signal. The receiver computes the characteristics of the received signal in the form of a ratio N.sub.k /g.sub.k, where g.sub.k is the channel gain (inverse of the attenuation) in frequency band k and N.sub.k is the noise power in the band k. The literature contains many algorithms for determining the power distribution across the full frequency bandwidth for maximum data throughput. As noted above, the optimum approach for non-uniform Gaussian noise channel divided such that each band can be considered an additive white Gaussian noise channel has been proved to be the "water pouring" algorithm of power distribution. In this case, the g.sup..sub.k /N.sub.k. Profile is compared to a terrain and the available aggregate power limit to a fixed supply of water poured over the terrain. The depth of the water corresponds to the power spectral density. The water pouring analogy is inappropriate to allocation of power in digital channels intended for transmission of binary data (bits).
According to one method of allocating bits (John A. C. Bingham, Multicarrier Modulation for Data Transmission: An Idea Whose Time Has Come, IEEE Communications Magazine, May 1990, pp5-14), frequency sub-bands or bins are "filled" with data bits one bit at a time. A bit is added to the bin for which the marginal power cost is the lowest. That is, a bit is added to the bin such that transmission in that bin is the least expensive, relative to an additional bit in any other bin, in terms of power needed for the resulting signal constellation to be received at a predefined BER. The filling procedure is followed until the total Power Budget is used up. Since power can only be allocated in discrete amounts corresponding to each bit, the procedure is likened, as mentioned, to an ice-cube filling procedure rather than a water-filling procedure.